package heaps

import "fmt"

/**
堆的定义
一颗完全二叉树
每个节点的值大于等于（或小于等于）其子树中每个节点的值
大顶堆，小顶堆

堆的存储
树的存储方式一般有链式存储和线性存储，分别对应我们常见的链表和数组两种方式，对于完全二叉树而言，用数组来存储是非常节省存储空间的，因为不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点，
*/

/**
      7
   /     \
  5       6
 / \     /  \
3   2   1    4
数组存储方式
[0,7,5,6,3,2,1,4]

// 其左子节点的索引满足
var leftIndex = 2 * i
// 其右子节点的索引满足
var rightIndex = 2 * i + 1
// 其父节点的索引满足
var parentIndex = i / 2


小顶堆求最大的topK
大顶堆求最小的topK
*/

type Heap struct {
	List     []int
	Capacity int
	SortType int8 //1为大顶推，-1为小顶堆
}

func NewHeap(cap int, sort int8) *Heap {
	return &Heap{
		List:     make([]int, 1), //为方便操作，第一个元素空出
		Capacity: cap + 1,
		SortType: sort,
	}
}

/*
新建一个元素
1.如果容量没满，那就插入到尾部，向上交换
2.如果容量没满，那么就删除顶元素，替换掉顶元素，然后向下交换
*/

func (h *Heap) Insert(val int) {
	//容量没满
	if h.Capacity > len(h.List) {
		h.List = append(h.List, val)
		idx := len(h.List) - 1
		h.up(idx)
	} else if h.Capacity == len(h.List) {
		if h.SortType > 0 && val < h.List[1] {
			h.List[1] = val
			h.down(1)
		} else if h.SortType < 0 && val > h.List[1] {
			h.List[1] = val
			h.down(1)
		}
	}
}

/*
删除一个元素，去掉顶部元素，然后将最底部最后一个元素，放到顶部，然后从顶部进行置换
*/

func (h *Heap) Push() int {
	var res int
	if len(h.List) > 2 {
		res = h.List[1]
		h.List[1] = h.List[len(h.List)-1]
		h.List = h.List[:len(h.List)-1]
		fmt.Println(h.List)
		h.down(1)
	} else if len(h.List) == 2 {
		res = h.List[1]
		h.List = h.List[0:1]
	}
	return res
}

/*
从底部向上交换
*/
func (h *Heap) up(idx int) {
	var parent int
	parent = idx / 2
	if parent == 0 {
		return
	}

	if h.SortType > 0 {
		if h.List[idx] > h.List[parent] {
			h.swap(&h.List[idx], &h.List[parent])
			h.up(parent)
		}
	} else {
		if h.List[idx] < h.List[parent] {
			h.swap(&h.List[idx], &h.List[parent])
			h.up(parent)
		}
	}
}

/*
从顶部向下交换
*/
func (h *Heap) down(parent int) {
	var (
		left  = parent * 2
		right = parent*2 + 1
	)
	ll := len(h.List) - 1

	if left < ll {
		if h.SortType > 0 {
			if h.List[left] > h.List[right] {
				if h.List[parent] < h.List[left] {
					h.swap(&h.List[parent], &h.List[left])
					h.down(left)
				}
			} else {
				if h.List[parent] < h.List[right] {
					h.swap(&h.List[parent], &h.List[right])
					h.down(right)
				}
			}
		} else if h.SortType < 0 {
			if h.List[left] < h.List[right] {
				if h.List[parent] > h.List[left] {
					h.swap(&h.List[parent], &h.List[left])
					h.down(left)
				}
			} else {
				if h.List[parent] > h.List[right] {
					h.swap(&h.List[parent], &h.List[right])
					h.down(right)
				}
			}
		}
	} else if left == ll {
		if h.SortType > 0 && h.List[parent] < h.List[left] {
			h.swap(&h.List[parent], &h.List[left])
			h.down(left)
		} else if h.SortType < 0 && h.List[parent] > h.List[left] {
			h.swap(&h.List[parent], &h.List[left])
			h.down(left)
		}
	}

	return
}

/*
交换
*/
func (h *Heap) swap(a, b *int) {
	tmp := *a
	*a = *b
	*b = tmp
}
